package sol.leetcode;

import java.util.Arrays;

/**
 * Kth Largest Element in an Array
 */
public class Issue215 {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, 0, nums.length - 1, k);
    }

    public int findKthLargest(int[] nums, int start, int end, int k) {
        if (start == end) return nums[start];        //只有一个数
        int m = partition(nums, start, end), cur = m - start + 1;
        if (k == cur) return nums[m];                        //刚好是第id个数
        else if (k < cur) return findKthLargest(nums, start, m - 1, k);//第id个数在左边
        else return findKthLargest(nums, m + 1, end, k - cur);


    }

    private int partition(int[] nums, int start, int end) {
        int pivot = nums[start];
        int i = start, j = start + 1;
        for (; j <= end; ++j) {
            if (nums[j] >= pivot)
                swap(nums, ++i, j);
        }
        swap(nums, start, i);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 5, 8, 6, 7};
        System.out.println(Arrays.toString(nums));
        Issue215 sol = new Issue215();
        //sol.partition(nums, 0, nums.length - 1);
        //System.out.println(Arrays.toString(nums));
        System.out.println(sol.findKthLargest(nums, 2));
    }
}
